package leetcode.editor.cn;
 
/**
 * 不同的二叉搜索树
 * @author qulq
 * @date 2024-07-23 20:50:20
 */
public class T96_UniqueBinarySearchTrees{
	 public static void main(String[] args) {
	 	 // 测试代码
	 	 Solution solution = new T96_UniqueBinarySearchTrees().new Solution();
	 }
	 
// 力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
	public int numTrees(int n) {
		// 初始化 dp 数组
		int[] dp = new int[n + 1];
		// 初始化0个节点和1个节点的情况
		dp[0] = 1;
		dp[1] = 1;
		for (int i = 2; i <= n; i++) {
			for (int j = 1; j <= i; j++) {
				// 对于第i个节点，需要考虑1作为根节点直到i作为根节点的情况，所以需要累加
				// 一共i个节点，对于根节点j时,左子树的节点个数为j-1，右子树的节点个数为i-j
				dp[i] += dp[j - 1] * dp[i - j];
			}
		}
		return dp[n];
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}